package datastructure.tree;

/**
 *
 * @author Lei Zhang
 */
public class FindLeastCommonAncester {


  /**
   * Without using parent point
   * assume p and q both exist
   * 
   */
  public static TreeNode findLeastCommonAncester(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) {
      return null;
    }

    if (root == p || root == q) {
      return root;
    } else {
      TreeNode nodeLeft = findLeastCommonAncester(root.left, p, q);
      TreeNode nodeRight = findLeastCommonAncester(root.right, p, q);

      if (nodeLeft != null && nodeRight != null) {
        return root;
      } else if (nodeLeft != null) {
        return nodeLeft;
      } else if (nodeRight != null) {
        return nodeRight;
      }

      return null;
    }
  }

  public static void main(String args[]) {

    TreeNode n1 = new TreeNode(1);
    TreeNode n2 = new TreeNode(2);
    TreeNode n3 = new TreeNode(3);
    TreeNode n4 = new TreeNode(4);
    TreeNode n5 = new TreeNode(5);
    TreeNode n6 = new TreeNode(6);

    TreeNode n7 = new TreeNode(7);


    n5.left = n2;
    n5.right = n6;
    n2.left = n1;
    n2.right = n4;
    n4.left = n3;

    TreeNode p = FindLeastCommonAncester.findLeastCommonAncester(n5, n1, n7);
    System.out.println(p.value);

  }
}
